#include "headfiles.h"

using namespace std;

int minDistance(string word1, string word2) {
    if (word1.empty()) {
        return word2.size();
    }
    
    if (word2.empty()) {
        return word1.size();
    }
    
    int *dist[2];
    dist[0] = new int[word2.size() + 1];
    dist[1] = new int[word2.size() + 1];
    int i, j;
    for (j = 0; j <= word2.size(); j++) {
        dist[0][j] = j;
    }
    
    for (i = 1; i <= word1.size(); i++) {
        dist[i & 1][0] = i;
        for (j = 1; j <= word2.size(); j++) {
            int dist0 = dist[(i - 1) & 1][j - 1] + ((word1[i - 1] == word2[j - 1]) ? 0 : 1);
            int dist1 = dist[(i - 1) & 1][j] + 1;
            int dist2 = dist[i & 1][j - 1];
            int min_dist = min(dist0, min(dist1, dist2));
            dist[i & 1][j] = min_dist;
        }
    }
    
    int min_dist = dist[(i - 1) & 1][word2.size()];
    
    delete dist[0];
    delete dist[1];
    
    return min_dist;
}
